package leetcode_1101_1200;

import java.util.*;

public class LeeCode_1129 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(shortestAlternatingPaths(5,
                new int[][]{{0, 1}, {1,2}, {2,3}, {3,4}}, new int[][]{{1,2},{2,3},{3,1}})));
        System.out.println(Arrays.toString(shortestAlternatingPaths(3, new int[][]{{0, 1}}, new int[][]{{2, 1}})));
    }
    private static int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int[] e : redEdges) {
            if (map.containsKey(e[0])){
                map.get(e[0]).add(new int[]{e[1], 0});
            }else {
                List<int[]> list = new ArrayList<>();
                list.add(new int[]{e[1], 0});
                map.put(e[0], list);
            }
        }
        for (int[] e : blueEdges) {
            if (map.containsKey(e[0])){
                map.get(e[0]).add(new int[]{e[1], 1});
            }else {
                List<int[]> list = new ArrayList<>();
                list.add(new int[]{e[1], 1});
                map.put(e[0], list);
            }
        }
        boolean[][] vis = new boolean[n][2];
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{0, 0});
        queue.add(new int[]{0, 1});
        int step = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] p = queue.pop();
                int now = p[0], pc = p[1];
                vis[now][pc] = true;
                if (ans[now] == -1){
                    ans[now] = step;
                }
                if (!map.containsKey(now))
                    continue;
                for (int[] next_ : map.get(now)) {
                    int next = next_[0], nc = next_[1];
                    if (vis[next][nc] || nc == pc)
                        continue;
                    queue.offer(new int[]{next, nc});
                }
            }
            step++;
        }
        return ans;
    }
}
